The current state of the art includes two classes of techniques for estimating motion vectors between two images. The first class includes block-matching-based motion estimation techniques where individual image sample values within a source image block are matched to individual image samples within a candidate target image block. Each candidate target image block is positioned to correspond to one location in a predefined search window. Block matching-based motion estimation are widely used in today's real-time digital video compression systems.
Block matching is an important tool used in various digital video applications that require local/global correspondences between different parts of one image, or between two different images. A few of the applications which use block matching in one form or another include compression, tracking, recognition, and video content analysis. A typical full search block matching-based motion compensation system requires 2N.sup.2 (N+2S).sup.2 additions/subtractions per picture element (pixel or pel), where N is the horizontal and vertical size of the source and target blocks over which matching is performed, and S defines the extent of the area (in pixel units) extending beyond the boundaries of the non-displaced target block. The size of the search domain is therefore a (N+2S).times.(N+2S) pixel area. The number of operations quoted above accounts for N.sup.2 subtractions and N.sup.2 additions to calculate and accumulate distortion values, respectively, assuming that distortion is given by the sum of absolute pixel value differences (the actual number of additions is N.sup.2-1; for simplicity, it is assumed that the actual number of additions is N.sup.2). This number accounts for the number of visited positions in the search domain which is equal to (N+2S).sup.2. Computation may be reduced to some extent by using a hierarchical approach:
Coarse block matching is performed on a small version of the image, obtained with some form of multi-resolutional analysis, followed by fine block matching with a much smaller search area on the original image.
The second class of techniques for estimating motion vectors between two images 15 includes integral projection techniques for block motion estimation. Integral projection is a technique in which two-dimensional image array matching is replaced by matching of two one-dimensional vectors obtained by averaging image sample values horizontally and vertically, respectively. In the target block, the image block in the previous image, averaging is performed over the block plus the search area around it. In the source block, the image block in the current image, averaging is performed over the block only. Current integral projection methods suffer from limitations in estimating large displacements because vertical and horizontal components are estimated from the same (N+2S).times.(N+2S) target area.
S. Cain and K. Sauer, "Efficient Block Motion Estimation Using integral projections", IEEE Visual Signal Processing Workshop, pages 258-263, September 1992 describe a technique for integral projection for block motion estimation in a video coding system. Their technique includes a multi-step approach which works as long as displacements are small. However, Cain et al. do not recognize that there are alternative approaches when the motion in the image is larger. In addition, they do not consider any extension of their concept to the problem of estimating global translational or affine motion parameters.
I. H. Lee and R. H. Park, "A Fast block matching Algorithm Using integral projections", Proceedings of TENCON 87, Vol. 2, Seoul, Korea, August 25-28, 1987, consider a fast method for doing integral projection in block matching. They propose a multi-step approach with the purpose to reduce the number of visited pixel locations. Like in the previous case, they do not consider other applications of the method. In their approach, the small displacement limitation is resolved by the fact that the integral projection they use performs averaging over the target block only. Consequently, a search is required to estimate each displacement vector as in any conventional block matching algorithm.
E. Ogura, Y. Ikenaga, Y. Iida, Y. Hosoya, M. Takashima, K. Yamashita, "A Cost Effective Motion Estimation Processor LSI Using a Simple and Efficient Algorithm", IEEE Transactions on Consumer Electronics, Vol. 41, No. 3, August 1995, consider various simplifications of the integral projection technique which involve further averaging of the column and row vectors. They also consider a general architecture which supports these simplifications as well as half-pel precision motion estimation. As in the two previous cases, they do not address other applications, and they use integral projection technique in conjunction with searching to make sure that large displacements may be estimated properly.